#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

vector<bool> isPrime;


/*
    埃氏筛
    时间: O(n*loglogn)
 */
void Era() {
    isPrime.resize(10000, 1);
    int n = isPrime.size();
    isPrime[0] = isPrime[1] = 0;

    for (int i = 2; i < n; i++) {
        if (isPrime[i]) {
            for (int j = i + i; j < n; j += i) isPrime[j] = 0;
        }
    }
}

/*
    欧拉筛
    时间: O(n)
    空间: O(n)
*/
vector<int> prime;
void Euler() {
    isPrime.resize(10000, 1);
    int n = isPrime.size();
    isPrime[0] = isPrime[1] = 0;
    for (int i = 2; i < n; i++) {
        if (isPrime[i]) prime.emplace_back(i);
        for (int j = 0; prime[j] * i < n; j++) {
            isPrime[prime[j] * i] = 0;
            if (i % prime[j] == 0) break;
        }
    }
}

int main() {
    // Era();
    Euler();
    for (int i = 0; i < isPrime.size(); i++) {
        if (isPrime[i]) cout << i << ", ";
    }
    return 0;
}